[LDPC Code]
Recently, as an error correction code (ECC), an LDPC (Low Density Parity Check) code has attracted attention (R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, January 1962.) The LDPC code is featured such that a parity checking matrix defining the code is sparsely arranged. A sparsely-arranged matrix represents a matrix in which the number of elements of “1” is configured to be small.
FIG. 1 is a diagram illustrating an example of a parity checking matrix of a (12,6) LDPC code.
The parity checking matrix H illustrated in FIG. 1 is a matrix in which the weight (the number of “1″s”) of each column is “3”, and the weight of each row is “6”. The encoding according to the LDPC code is realized by generating a generation matrix G based on the parity checking matrix H and generates a code word by multiplying the generation matrix G by binary information.
More specifically, an encoding device that performs encoding according to the LDPC calculates a generation matrix G that satisfies GHT=0 with a transposed matrix HT of the parity checking matrix H. Here, in a case where the generation matrix G is a k×n matrix, the encoding device multiplies the generation matrix G by information configured by k bits so as to generate a code word configured by n bits. In the code word generated by the encoding device, a code bit having a value of “0” is mapped into “+1” and a code bit having a value of “1” is mapped into “−1”, and the code word is transmitted and is received by the reception side through a predetermined communication line.
On the other hand, as a decoding method of the LDPC code, a method is known in which the parity checking matrix is represented as a bipartite graph, and the process is repeatedly performed while likelihood information is exchanged between a check node and a bit node.
FIG. 2 is a diagram illustrating a bipartite graph of the parity checking matrix H illustrated in FIG. 1.
White rectangles illustrated on the upper side of FIG. 2 represent check nodes, and white circles illustrated on the lower side represent bit nodes. The check node corresponds to a row of the parity checking matrix, and the bit node corresponds to a column of the parity checking matrix. In a case where elements, which are other than “0”, of the parity checking matrix H are associated with connections between nodes, as illustrated in FIG. 2, the check nodes and the bit nodes are connected to each other at the edges.
[BP Decoding in Related Art]
Here, BP (Belief Propagation) decoding as one of methods of decoding the LDPC code will be described.
Here, a code bit length is denoted by N, and a parity checking matrix having the number of parity checking rows of M is denoted by H=[Hmn]. In addition, m denotes the row number (check node number) and has a value in the range of 0≦m<M. Furthermore, n denotes a column number (bit node number) and has a value in the range of 0≦n≦N. In addition, a set of bit numbers used for the m-th parity checking calculation is denoted by N(m)={n|Hmn=1}, and a set of the parity checking numbers for which a parity checking operation is performed by using the n-th bit is denoted by M(n)={mβHmn=1}. N(m)={n|Hmn=1} represents a set of bit nodes connected to the m-th check node (check node m), and M(n)={m|Hmn=1} represents a set of check nodes connected to the n-th bit node (bit node n).
The initial likelihood acquired from the reception value of the n-th bit is denoted by Fn, the likelihood from the check node m to the bit node n in the i-th decoding process is denoted by εmn(i), and the likelihood from the bit node n to the check node m n in the i-th decoding process is denoted by zmn(i). In addition, the posterior likelihood of bit n acquired by the i-th decoding process is denoted by zn(i). The repeated decoding is realized by repeatedly performing a decoding process for the maximum number of times set in advance. In such a case, the BP decoding is represented as below.
Initialization:
An LDPC decoding circuit sets 1 to i.
The LDPC decoding circuit sets Fn to each zmn(0).
Step 1:
(i) Check Node Calculating
The LDPC decoding circuit acquires εmn(i) by using the following Equations (1) and (2) for all the values of n and all the values of m satisfying “m∈M(n)”. In Equation (1), n′ represents a bit node acquired by excluding n from the bit nodes included in N(m).
                              τ          mn                      (            i            )                          =                              ∏                                          n                ′                            ∈                                                N                  ⁡                                      (                    m                    )                                                  ⁢                \n                                                                                    ⁢                                          ⁢                      tanh            ⁡                          (                                                z                                      mn                    ′                                                        (                                          i                      -                      1                                        )                                                  /                2                            )                                                          (        1        )                                          ɛ          mn                      (            i            )                          =                  log          ⁢                                          ⁢                                    1              +                              τ                mn                                  (                  i                  )                                                                    1              -                              τ                mn                                  (                  i                  )                                                                                        (        2        )            (ii) Bit Node Calculating
For all the values of m and all the values of n satisfying “n∈N(m)”, the LDPC decoding circuit acquires zmn(i) by using the following Equation (3) and acquires zn(i) by using the following Equation (4). In Equation (3), m′ represents check nodes acquired by excluding m from the check nodes included in M(n).
                              z          mn                      (            i            )                          =                              F            n                    +                                    ∑                                                m                  ′                                ∈                                                      M                    ⁡                                          (                      n                      )                                                        ⁢                  \                  ⁢                  m                                                      ⁢                                                  ⁢                                          ɛ                                                      m                    ′                                    ⁢                  n                                                  (                  i                  )                                                                                                                                    (        3        )                                          z          n                      (            i            )                          =                              F            n                    +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                                                  ⁢                                          ɛ                mn                                  (                  i                  )                                                                                                                                    (        4        )            Step 2:(i) Hard Decision
The LDPC decoding circuit performs a hard decision as wn(i)=1 in a case where zn(i)>0 and as wn(i)=0 in a case where zn(i)<0. In addition, the LDPC decoding circuit acquires a determination value vector w(i)=[wn(i)] that has hard decision values (bit determining values) as its elements based on the result of the hard decision.
(ii) Decoding Ending Condition Determining
The LDPC decoding circuit performs a parity checking calculation that is the calculation of a parity checking equation Hw(i). In a case where the parity checking equation Hw(i)=0 is satisfied, in other words, in a case where the following Equation (5) is satisfied for 0≦m<M, or in a case the number i of repetitions of the decoding process arrives at the maximum number of times set in advance, the LDPC decoding circuit performs the process of Step 3. On the other hand, in the other cases, the LDPC decoding circuit increases i by one and performs the process of Step 1.
                                          ∑                          n              ∈                              N                ⁡                                  (                  m                  )                                                              ⁢                                    H              mn                        ⁢                          w              n                              (                i                )                                                    =        0                            (        5        )            Step 3:
The LDPC decoding circuit outputs a determination value vector w(i) as a result of the decoding process.
In the BP decoding, after all the check node calculations are completed in the first decoding process as described above, all the bit node calculations are performed. In other words, εmn(i) in the check node calculating of Step 1 (i) is acquired, and zmn(i) and zn(i) are acquired in the bit node calculating of (ii) by using the result thereof.
[Group Shuffled BP Decoding in Related Art]
However, in the repeated decoding of the LDPC code, a method for decreasing the number of times until the decoding converges is proposed (J. Zhang and M. Fossorier, “Shuffled belief propagation decoding” Proc. 36th Annu. Asilomar Conf. Signals, Syst., Computers, pp. 8-15, November 2002 and M. M. Mansour and N. R. Shanbhag, “Turbo decoder architecture for low-density parity-check codes” Proc. Global Telecommun. Conf., pp. 1383-1388, November 2002).
In J. Zhang and M. Fossorier, “Shuffled belief propagation decoding” Proc. 36th Annu. Asilomar Conf. Signals, Syst., Computers, pp. 8-15, November 2002, group shuffled BP decoding in which the bit node calculating is performed in a divisional manner is described. In addition, in JP-T-2008-527760, a decoding circuit in which replica coupling is formed by using a plurality of group shuffled BP decoding circuits is disclosed. In addition, in JP-A-2008-16959, a decoding device and a decoding method that can effectively perform decoding by changing the update schedule of the likelihood in a shuffled BP decoding circuit are disclosed.
Next, group shuffled BP decoding will be described. The group shuffled BP decoding is represented as bellows. The number of groups dividing the bit nodes is denoted by G, and it is assumed that the number of bit nodes processed in each group is Ng=N/G.
Initialization:
An LDPC decoding circuit sets 1 to i.
The LDPC decoding circuit sets Fn to each zmn(0).
Step 1:
The LDPC decoding circuit repeats (i) check node calculating and (ii) bit node calculating while changing a variable g representing the group of bit nodes as a processing target from 0 to G−1. In other words, the LDPC decoding circuit performs the check node calculating and the bit node calculating for the first group out of G check node groups as a target. Next, the LDPC decoding circuit performs the check node calculating and the bit node calculating for the second group as a target and thereafter, performs the check node calculating and the bit node calculating by sequentially setting the third group and a group after that as a target.
(i) Check Node Calculating
The LDPC decoding circuit acquires εmn(i) by using the following Equations (6) and (7) for n satisfying “gNg≦n<(g+1)Ng” and m satisfying “m∈M(n)”.
                              τ          mn                      (            i            )                          =                              (                                          ∏                                                                            n                      ′                                        ∈                                                                  N                        ⁡                                                  (                          m                          )                                                                    ⁢                      \n                                                                                                  n                      ′                                        <                                          gN                      g                                                                                                                                    ⁢                                                          ⁢                              tanh                ⁡                                  (                                                            z                                              mn                        ′                                                                    (                        i                        )                                                              /                    2                                    )                                                      )                    ⁢                      (                                          ∏                                                                            n                      ′                                        ∈                                                                  N                        ⁡                                                  (                          m                          )                                                                    ⁢                      \n                                                                                                  n                      ′                                        ≧                                          gN                      g                                                                                                                                    ⁢                                                          ⁢                              tanh                ⁡                                  (                                                            z                                              mn                        ′                                                                    (                                                  i                          -                          1                                                )                                                              /                    2                                    )                                                      )                                              (        6        )                                          ɛ          mn                      (            i            )                          =                  log          ⁢                                          ⁢                                    1              +                              τ                mn                                  (                  i                  )                                                                    1              -                              τ                mn                                  (                  i                  )                                                                                        (        7        )            (ii) Bit Node Calculating
For n satisfying “gNg≦n<(g+1)Ng” and m satisfying “m∈M(n)”, the LDPC decoding circuit acquires zmn(i) by using the following Equation (8) and acquires zn(i) by using the following Equation (9).
                              z          mn                      (            i            )                          =                              F            n                    +                                    ∑                                                m                  ′                                ∈                                                      M                    ⁡                                          (                      n                      )                                                        ⁢                  \                  ⁢                  m                                                      ⁢                                                  ⁢                                          ɛ                                                      m                    ′                                    ⁢                  n                                                  (                  i                  )                                                                                                                                    (        8        )                                          z          n                      (            i            )                          =                              F            n                    +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                                                  ⁢                                          ɛ                mn                                  (                  i                  )                                                                                                                                    (        9        )            Step 2:(i) Hard Decision
The LDPC decoding circuit performs a hard decision as wn(i)=1 in a case where zn(i)>0 and as wn(i)=0 in a case where zn(i)<0. In addition, the LDPC decoding circuit acquires a determination value vector w(i)=[wn(i)] based on the result of the hard decision.
(ii) Decoding Ending Condition Determining
In a case where the parity checking equation Hw(i)=0 is satisfied, in other words, in a case where the following Equation (10) is satisfied for 0≦m<M, or in a case the number of repetitions of the decoding process arrives at the maximum number of times set in advance, the LDPC decoding circuit performs the process of Step 3. On the other hand, in the other cases, the LDPC decoding circuit increases i by one and performs the process of Step 1.
                                          ∑                          n              ∈                              N                ⁡                                  (                  m                  )                                                              ⁢                                    H              mn                        ⁢                          w              n                              (                i                )                                                    =        0                            (        10        )            Step 3:
The LDPC decoding circuit outputs a determination value vector w(i) as a result of the decoding process.
FIG. 3 is a block diagram illustrating the configuration of an LDPC decoding circuit that performs the above-described group shuffled BP decoding.
The LDPC decoding circuit 1 illustrated in FIG. 3 is configured by a check node calculating circuit 11, a bit node calculating circuit 12, a hard decision circuit 13, a parity checking circuit 14, and an output circuit 15. To the checking node calculating circuit 11 and the bit node calculating circuit 12, the initial likelihood Fn that is acquired from the reception value of the n-th bit is input.
The check node calculating circuit 11 acquires εmn(i) by performing the check node calculating for a predetermined group of bit nodes as a target as described in the process of Step 1 (i). The check node calculating circuit 11 outputs εmn(i) to the bit node calculating circuit 12.
The bit node calculating circuit 12, as described as the process of Step 1 (ii), acquires zmn(i) and zn(i) by performing the bit node calculating. The bit node calculating circuit 12 outputs zn(i) to the hard decision circuit 13 and outputs zmn(i) and zmn(i−1) acquired from the previous ((i−1)-th) repeated decoding to the check node calculating circuit 11.
The hard decision circuit 13, as described as the process of Step 2 (i) performs a hard decision. The hard decision circuit 13 outputs the determination value vector wn(i) to the parity checking circuit 14 and the output circuit 15.
The parity checking circuit 14, as described as the process of Step 2 (ii), decoding ending condition determining is performed. The parity checking circuit 14 performs the decoding ending condition determining once every time when the bit node calculating for N bit nodes, which is the same as the code bit length, is completed. In a case where the parity checking equation Hw(i)=0 is not satisfied, and when the number of repetitions of the decoding process has not arrived at the maximum number of times set in advance, the decoding ending condition is determined not to be satisfied. On the other hand, in a case where the parity checking equation Hw(i)=0 is satisfied, or the number of repetitions of the decoding process has arrived at the maximum number of times set in advance, the decoding ending condition is determined to be satisfied.
In a case where the decoding ending condition is determined not to be satisfied, the parity checking circuit outputs a control signal instructing to increase the variable i by one and repeat the decoding process to the check node calculating circuit 11 and the bit node calculating circuit 12. On the other hand, in a case where the decoding ending condition is determined to be satisfied, the parity checking circuit 14 outputs a signal indicating it to the output circuit 15.
In a case where the signal that indicates that the decoding ending condition is satisfied is supplied from the parity checking circuit 14, the output circuit 15 outputs the determination value vector wn(i) as a result of the decoding.
[Layered BP Decoding in Related Art]
In M. M. Mansour and N. R. Shanbhag, “Turbo decoder architecture for low-density parity-check codes” Proc. Global Telecommun. Conf., pp. 1383-1388, November 2002, a decoding method known as turbo decoding or layered BP decoding is disclosed in which the check node calculating is performed by being divided into a plurality of processes. Next, the layered BP decoding will be described. The layered BP decoding is represented as below.
Initialization:
An LDPC decoding circuit sets 1 to i.
The LDPC decoding circuit sets 0 to each εmn(0).
Step 1:
The LDPC decoding circuit repeats (i) check node calculating and (ii) bit node calculating, while changing a variable m representing the check node as a processing target from 0 to M−1.
(i) Bit Node Calculating
For n satisfying “n∈N(m)”, the LDPC decoding circuit acquires zmn(i−1) by using the following Equation (11).
                              z          mn                      (                          i              -              1                        )                          =                              F            n                    +                                    ∑                                                                    m                    ′                                    ∈                                      M                    ⁡                                          (                      n                      )                                                                                                            m                    ′                                    <                  m                                                      ⁢                                          ɛ                                                      m                    ′                                    ⁢                  n                                                  (                  i                  )                                                                                                          +                                    ∑                                                                    m                    ′                                    ∈                                      M                    ⁡                                          (                      n                      )                                                                                                            m                    ′                                    >                  m                                                      ⁢                          ɛ                                                m                  ′                                ⁢                n                                            (                                  i                  -                  1                                )                                                                        (        11        )            (ii) Check Node Calculating
The LDPC decoding circuit acquires εmn(i) by using the following Equations (12) and (13) for n satisfying “n∈N(m)”.
                              τ          mn                      (            i            )                          =                              ∏                                          n                ′                            ∈                                                N                  ⁡                                      (                    m                    )                                                  ⁢                \n                                              ⁢                                          ⁢                      tanh            ⁡                          (                                                z                                      mn                    ′                                                                              (                                              i                        -                        1                                            )                                        ⁢                                                                                                                /                2                            )                                                          (        12        )                                          ɛ          mn                      (            i            )                          =                  log          ⁢                                          ⁢                                    1              +                              τ                mn                                  (                  i                  )                                                                    1              -                              τ                mn                                  (                  i                  )                                                                                        (        13        )            Step 2:(i) Hard Decision
The LDPC decoding circuit acquires zn(i) for all the values of n by using the following Equation (14).
                              z          n                      (            i            )                          =                              F            n                    +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                                                                    ⁢                          ɛ              mn                              (                i                )                                                                        (        14        )            
In addition, the LDPC decoding circuit performs a hard decision as wn(i)=1 in a case where zn(i)>0 and as wn(i)=0 in a case where zn(i)<0. Furthermore, the LDPC decoding circuit acquires a determination value vector w(i)=[wn(i)] based on the result of the hard decision.
(ii) Decoding Ending Condition Determining
In a case where the parity checking equation Hw(i)=0 is satisfied, in other words, in a case where the following Equation (15) is satisfied for 0≦m<M, or in a case the number i of repetitions of the decoding process arrives at the maximum number of times set in advance, the LDPC decoding circuit performs the process of Step 3. On the other hand, in the other cases, the LDPC decoding circuit increases i by one and performs the process of Step 1.
                                          ∑                          n              ∈                              N                ⁡                                  (                  m                  )                                                                                                    ⁢                                    H              mn                        ⁢                          w              n                              (                i                )                                                    =        0                            (        15        )            Step 3:
The LDPC decoding circuit outputs a determination value vector w(i) as a result of the decoding process.
In Timo Lehnigk-Emden, Norbert When and Friedbert Berens, “Enhanced iteration control for ultra low power LDPC decoding” proceedings of ICT-MobileSummit 2008, a technique is disclosed in which it is determined before the repetition of the decoding process whether or not the hard decision of a reception word satisfies the condition of a code word, and the decoding process is not repeated in a case where the condition of the code word is satisfied.